package com.yubest;

import java.util.Arrays;

/**
 * 排序算法
 *
 * [图片] img/sort.png
 *
 * 参考 https://github.com/hustcc/JS-Sorting-Algorithm
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/12/2 14:40
 */
public class Sort {

    public static void main(String[] args) {

        int[] nums = {1, 5, 6, 7, 4, 9, 2, 8, 3, 0, 3, 3, 2};

        System.out.println(Arrays.toString(new Sort().bubbleSort(Arrays.copyOf(nums, nums.length))));

        System.out.println(Arrays.toString(new Sort().selectionSort(Arrays.copyOf(nums, nums.length))));

        System.out.println(Arrays.toString(new Sort().insertionSort(Arrays.copyOf(nums, nums.length))));

        System.out.println(Arrays.toString(new Sort().quickSort(Arrays.copyOf(nums, nums.length))));

        System.out.println(Arrays.toString(new Sort().shellSort(Arrays.copyOf(nums, nums.length))));

        System.out.println(Arrays.toString(new Sort().mergeSort(Arrays.copyOf(nums, nums.length))));

        System.out.println(Arrays.toString(new Sort().heapSort(Arrays.copyOf(nums, nums.length))));

        System.out.println(Arrays.toString(new Sort().countSort(Arrays.copyOf(nums, nums.length))));
    }

    /**
     * 冒泡排序
     *
     * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     *
     * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
     *
     * 针对所有的元素重复以上的步骤，除了最后一个。
     *
     * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     *
     * @param nums
     * @return
     */
    public int[] bubbleSort(int[] nums) {
        for (int p = nums.length - 1; p > 0; p--) {
            for (int i = 0; i < p; i++) {
                if (nums[i] > nums[i + 1]) {
                    swap(nums, i, i + 1);
                }
            }
        }
        return nums;
    }

    /**
     * 选择排序
     *
     * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
     *
     * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     *
     * 重复第二步，直到所有元素均排序完毕。
     *
     * @param nums
     * @return
     */
    public int[] selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    swap(nums, i, j);
                }
            }
        }
        return nums;
    }

    /**
     * 插入排序
     *
     * 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
     *
     * 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
     *
     * @param nums
     * @return
     */
    public int[] insertionSort(int[] nums) {
        int t;
        for (int i = 0; i < nums.length; i++) {
            t = nums[i];
            for (int j = i; j > 0; j--) {
                if (t >= nums[j - 1]) {
                    nums[j] = t;
                    break;
                }
                nums[j] = nums[j - 1];
            }
        }
        return nums;
    }

    /**
     * 希尔排序
     *
     *
     * 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
     *
     * 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
     *
     * 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
     * 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
     * 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
     *
     *
     * 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
     *
     * 按增量序列个数 k，对序列进行 k 趟排序；
     *
     * 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     *
     * @param nums
     * @return
     */
    public int[] shellSort(int[] nums) {
        //增量为2
        for (int gap = nums.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < nums.length; i++) {
                for (int j = i; j - gap >= 0; j -= gap) {
                    if (nums[j] < nums[j - gap]) {
                        swap(nums, j, j - gap);
                    }
                }
            }
        }
        return nums;
    }

    /**
     * 归并排序
     *
     *
     * 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
     *
     *
     * 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
     *
     * 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
     *
     * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
     *
     * 重复步骤 3 直到某一指针达到序列尾；
     *
     * 将另一序列剩下的所有元素直接复制到合并序列尾。
     *
     * @param nums
     * @return
     */
    public int[] mergeSort(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }
        int i = nums.length / 2;
        int[] nums1 = mergeSort(Arrays.copyOfRange(nums, 0, i));
        int[] nums2 = mergeSort(Arrays.copyOfRange(nums, i, nums.length));
        return mergeSort(nums1, nums2);
    }

    private int[] mergeSort(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length + nums2.length];
        int i = 0, p1 = 0, p2 = 0;
        while (p1 < nums1.length && p2 < nums2.length) {
            nums[i++] = nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++];
        }
        if (p1 < nums1.length) {
            System.arraycopy(nums1, p1, nums, i, nums1.length - p1);
        }
        if (p2 < nums2.length) {
            System.arraycopy(nums2, p2, nums, i, nums2.length - p2);
        }
        return nums;
    }


    /**
     * 快速排序
     *
     * 从数列中挑出一个元素，称为 “基准”（pivot）;
     *
     * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
     *
     * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
     *
     * 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
     *
     * @param nums
     * @return
     */
    public int[] quickSort(int[] nums) {
        return quickSort(nums, 0, nums.length - 1);
    }

    private int[] quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int pivot = start;
            for (int i = start + 1; i <= end; i++) {
                //nums[start]作为基准值
                if (nums[i] < nums[start]) {
                    swap(nums, i, ++pivot);
                }
            }
            swap(nums, start, pivot);
            quickSort(nums, start, pivot - 1);
            quickSort(nums, pivot + 1, end);
        }
        return nums;
    }

    /**
     * 堆排序
     *
     *
     * 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
     *
     * 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
     * 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
     *
     * 如果 k 从 0 开始：
     * 第 k 个节点的左子节点为 2 * k + 1
     * 第 k 个节点的右子节点为 2 * k + 2
     * 第 k 个节点的父节点为 (k - 1) / 2
     *
     * 如果 k 从 1 开始：
     * 第 k 个节点的左子节点为 2 * k
     * 第 k 个节点的右子节点为 2 * k + 1
     * 第 k 个节点的父节点为 k / 2
     *
     * 将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
     *
     * 把堆首（最大值）和堆尾互换；
     *
     * 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
     *
     * 重复步骤 2，直到堆的尺寸为 1。
     *
     * @param nums
     * @return
     */
    public int[] heapSort(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            //构建大顶堆
            heapSort(nums, i + 1);
            //将堆顶的元素替换到数组尾
            swap(nums, 0, i);
        }
        return nums;
    }

    private void heapSort(int[] nums, int length) {
        //找到最后一个非叶子节点
        int k = (length - 1) / 2;
        int left, right;
        for (int i = k; i >= 0; i--) {
            left = 2 * i + 1;
            right = 2 * i + 2;
            if (left < length && nums[i] < nums[left]) {
                swap(nums, i, left);
            }
            if (right < length && nums[i] < nums[right]) {
                swap(nums, i, right);
            }
        }
    }

    /**
     * 计数排序
     *
     * 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
     *
     * @param nums
     * @return
     */
    public int[] countSort(int[] nums) {
        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }
        int[] nums1 = new int[max + 1];
        for (int num : nums) {
            nums1[num]++;
        }
        int[] nums2 = new int[nums.length];
        for (int i = 0, j = 0; i < nums1.length; i++) {
            if (nums1[i] > 0) {
                for (int k = nums1[i]; k > 0; k--) {
                    nums2[j++] = i;
                }
            }
        }
        return nums2;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

}
